package mashibing.class16;

import java.util.*;

/**
 * 拓扑排序
 */
public class Class16_3_TopologySort {

    // directed graph and no loop
    public static List<Node> sortedTopology(Graph graph) {
        // key 某个节点   value 剩余的入度
        Map<Node, Integer> map = new HashMap<>();
        // 只有剩余入度为0的点，才进入这个队列
        Queue<Node> queue = new LinkedList<>();
        for (Node node : graph.nodes.values()) {
            if(node.in == 0) {
                queue.add(node);
            }
            map.put(node, node.in);
        }
        List<Node> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            res.add(poll);
            for (Node next : poll.nexts) {
                map.put(next, map.get(next) - 1);
                if(map.get(next) == 0) {
                    queue.add(next);
                }
            }
        }
        return res;
    }
}
